package TenkindsOfAlgorithm;

import java.awt.*;
import java.util.ArrayList;
import java.util.Collections;

/**
 * 2021/10/08
 * 解决思路：
 *      1）创建棋盘chessBoard，是一个二维数组
 *      2）将当前位置设置为已经访问，然后根据当前位置，计算马儿还能走哪些位置，并放到一个集合中，最多有八个位置，每走一步，step+1
 *      3）遍历ArrayList中存放的所有位置，看看那个可以走通，继续走，走不通就回朔
 *      3）判断马儿是否完成任务，使用STEP 和 finished 。 如果STEP没有达到棋盘个数，表示没有完成任务，走过的位置置0。
 *
 */

public class ChessBoard {
    private static int X; //棋盘列数
    private static int Y; //棋盘行数
    private static boolean visited[]; //标记棋盘的各个位置是否访问过
    private static boolean finished; // 为true则成功
    private static int STEP = 0;

    public static void main(String[] args) {
        System.out.println("骑士周游：");
        X = 10;
        Y = 4;
        int row = 2; //骑士初始行
        int col = 6; //骑士初始列
        //创建棋盘
        int[][] chessboard = new int[X][Y];
        //初始值都为false
        visited = new boolean[X * Y];
        long start = System.currentTimeMillis();
        traversalChessboard(chessboard, row -1, col - 1);
        long end = System.currentTimeMillis();
        System.out.println("共耗时 " + (end - start) + " 毫秒");

        //输出棋盘情况
        for (int[] rows : chessboard) {
            for (int step : rows) {
                System.out.print(step + "\t");
            }
            System.out.println();
        }
        System.out.println(STEP);

    }


    /**
     * 骑士周游算法
     * @param chessboard 棋盘(棋盘的每个格子记录的是骑士第几部访问的该位置)
     * @param row 骑士当前位置的行
     * @param col 骑士当前位置的列
     * @param //step 当前骑士走的是第几步，初始时为1
     */
    public static void traversalChessboard(int[][] chessboard, int row, int col){
        //记录骑士第step步访问该位置
        chessboard[row][col] = STEP++;
        //将该位置记录为已访问
        visited[row * Y + col] = true;
        //获取当前位置可以走的下一个位置的集合
        ArrayList<Point> next = next(new Point(col, row));
        //对next进行排序  排序的规则就是对ps的所有的Point对象的下一步的位置的数目，进行非递减排序
        sort(next);

        while (!next.isEmpty()){
            //取出骑士下一个走的位置
            Point p = next.remove(0);
            //判断下一个位置是否已经访问过，没有访问则访问 x与y是相对反的在Point类中
            if(!visited[p.y * X + p.x]){
                traversalChessboard(chessboard, p.y, p.x);
            }
        }

        //判断骑士是否完成周游，如果骑士走的步数小于 X * Y 则表示没有完成任务，此时，将整个棋盘置0
        //step < X * Y有两种情况：1.棋盘还没有走完  2.棋盘此时正在回溯
        if(STEP < X * Y  &&finished==false){
            chessboard[row][col] = 0;
            visited[row * X + col] = false;
            STEP--;
        }else {
            finished = true;
        }

    }

    /**
     * 根据当前的位置(Point为java的内置对象)，计算骑士下一步能走的位置，最多有8个位置
     * @param curPoint
     * @return 包含当前位置能访问的下一个位置的坐标！！！(坐标横着的是X轴！！！)
     */
    public static ArrayList<Point> next(Point curPoint){
        ArrayList<Point> nextList = new ArrayList<>();
        Point p = new Point();

        //表示骑士可以走5这个位置
        if((p.x = curPoint.x - 2) >= 0 && (p.y = curPoint.y - 1) >= 0){
            nextList.add(new Point(p));
        }

        //表示骑士可以走6这个位置
        if((p.x = curPoint.x - 1) >= 0 && (p.y = curPoint.y - 2) >= 0){
            nextList.add(new Point(p));
        }

        //表示骑士可以走7这个位置
        if((p.x = curPoint.x + 1) < X && (p.y = curPoint.y - 2) >= 0){
            nextList.add(new Point(p));
        }

        //表示骑士可以走0这个位置
        if((p.x = curPoint.x + 2) < X && (p.y = curPoint.y - 1) >= 0){
            nextList.add(new Point(p));
        }

        //表示骑士可以走1这个位置
        if((p.x = curPoint.x + 2) < X && (p.y = curPoint.y + 1) < Y){
            nextList.add(new Point(p));
        }

        //表示骑士可以走2这个位置
        if((p.x = curPoint.x + 1) < X && (p.y = curPoint.y + 2) < Y){
            nextList.add(new Point(p));
        }

        //表示骑士可以走3这个位置
        if((p.x = curPoint.x - 1) >= 0 && (p.y = curPoint.y + 2) < Y){
            nextList.add(new Point(p));
        }

        //表示骑士可以走4这个位置
        if((p.x = curPoint.x - 2) >= 0 && (p.y = curPoint.y + 1) < Y){
            nextList.add(new Point(p));
        }

        return  nextList;
    }
    //根据当前这一步的所有的下一步的选择位置，进行非递减排序，减少回溯的次数
    private static void sort(ArrayList<Point> nextList){
        Collections.sort(nextList,(o1,o2)->{
            int count1 = next(o1).size();
            int count2 = next(o2).size();
            return count1-count2;
        });
    }



}
